In computer science, a holographic algorithm is an algorithm that uses a holographic reduction. A holographic reduction is a reduction that preserves the number of solutions via a holographic transformation, also called a basis transformation. These concepts were introduced by Leslie Valiant[1] and are a natural type of reduction for #P problems.
Holographic algorithms can obtain exponential speedup on certain classes of problems. They have received notable coverage due to speculation that they are relevant to the P versus NP problem[2] and their impact on computational complexity theory.
The algorithms are unrelated to laser holography, except metaphorically. Their power comes from the mutual cancellation of many contributions to a sum, analogous to the interference patterns in a hologram.[2] Holographic algorithms have some similarities with quantum computation, but they use classical computation.[3]
The algorithms are based on several concepts: counting perfect matchings, holographic reduction of sets of problems, and reduction to perfect matching problems.[2]
The number of perfect matchings in a planar graph can be computed in polynomial time by using the FKT algorithm, dating to the 1960s. The FKT algorithm converts the problem into a Pfaffian computation, which can be solved polynomially using standard determinant algorithms. Note that although the basic formula for the determinant contains n! terms, the structure of the determinant allows it to be computed in polynomial time, as many terms cancel out and don't need to be computed. This cancellation is a key to holographic algorithms.
The second concept in holographic algorithms is reducing a problem to a different problem via holographic reduction. A standard technique in complexity is many-one reduction, so an instance of a problem is reduced to an instance of a (hopefully simpler) problem. However, holographic reductions between two computational problems preserve the sum of solutions without preserving correspondences between solutions.[1] For instance, the total number of solutions in both sets can be preserved, even though individual problems don't have matching solutions. The sum can also be weighted, rather than simply counting the number of solutions, using linear basis vectors. [4]
The holographic reduction uses matchgates, which are graph-theoretic entities, analogous to logic gates, that use perfect matching to perform operations. The matchgates are combined into a planar graph called a matchgrid. By Valiant's Holant Theorem, the (polynomial-time) perfect matching algorithm gives the solution to the matchgrid problem. Thus, the original problem is solved in polynomial time. [3]
Holographic algorithms have been used to find polynomial solutions to problems without formerly-known polynomial solutions in satisfiability, vertex cover, and other graph problems.[4] Although some of these problems are related to NP-complete problems, they are not themselves NP-complete, and thus do not prove P=NP.[4] Also, some of the solved problems are argued to be contrived (such as '#7Pl-Rtw-Mon-3CNF').[4]
A key research area is extending holographic algorithms to new problems.